package dailyTopic;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhangmin
 * @create 2021-08-06 9:51
 */
public class shortestPathLength847 {
    public int shortestPathLength(int[][] graph) {
        int n=graph.length;
        Queue<int[]> queue=new LinkedList<>();
        boolean[][] visited=new boolean[n][1<<n];
        for (int i = 0; i < n; i++) {
            queue.offer(new int[]{i,1<<i,0});
            visited[i][1<<i]=true;
        }
        int res=0;
        while (!queue.isEmpty()){
            int[] t=queue.poll();
            int u=t[0],m=t[1],d=t[2];
            if (m==(1<<n)-1){
                res=d;
                break;
            }
            for (int v:graph[u]){
                int mv=m|(1<<v);
                if (!visited[v][mv]){
                    queue.offer(new int[]{v,mv,d+1});
                    visited[v][mv]=true;
                }
            }
        }
        return res;
    }
}
